The present invention generally relates to asynchronous transfer mode (ATM) networks. In particular, the present invention relates to ATM networks that allow new virtual circuits to be introduced into virtual paths at intermediate network elements rather than only at a source network element.
ATM networks can provide substantial performance increases over more traditional time division multiplexing (TDM) networks (also known as synchronous transfer mode or STM networks). This is especially true when the networks must carry many different types of information (e.g., data, voice, and video). Information travelling over an ATM network is coded into 53-byte cells. The first 5 bytes of each cell are the cell header and contain important information about the cell, including the routing information (i.e., destination address) for the cell.
One of the main concepts of the ATM protocol is the virtual path. A virtual path represents a set of physical connections assigned to carry cells that share higher-order address bits. Virtual paths contain one or more virtual circuits. A virtual circuit represents a set of physical connections assigned to carry cells that share lower-order address bits. A virtual path may generally be thought of as a bundle of one or more virtual circuits.
Another important concept within the ATM protocol is the quality of service (QoS). A QoS class defines parameters that represent a minimal level of network performance for the traffic carried by links that are designated as providing that particular QoS. Thus, for any two network elements within a network, there may need to be as many links (virtual paths and virtual circuits) set up between them as there are QoS classes defined for that network.
When performing bandwidth allocation, network elements within an ATM network will perform statistical multiplexing with respect to a given virtual path. That is, bandwidth allocation is performed using statistical probabilities determined from historic usage information. The statistical multiplexing performance of a given network element is inversely proportional to the number of virtual paths incident upon that network element. Put another way, as bandwidth fragmentation increases at a given network element, the statistical multiplexing ability of that network element decreases.
FIG. 1 shows an arrangement of virtual paths within an ATM network 100 connecting network elements 102, 104, 106 and 108. The figure also shows virtual paths 110, 112, and 114, as well as virtual circuits 116, 118 and 120.
The virtual paths 110, 112 and 114 contain a number of virtual circuits, such as the virtual circuits 116, 118 and 120, respectively. In the arrangement of virtual paths shown in FIG. 1, there is one virtual path defined between a source network element 102 and each of the possible destination network elements 104, 106 and 108. After a virtual path, such as the virtual path 114, leaves a source network element, such as the network element 102, it may pass through one or more intermediate network elements, such as the network elements 104 and 106, as it continues to a destination network element, such as the network element 108.
Note that a network element may be an intermediate network element with respect to some virtual paths, but not with respect to other virtual paths. A network element is an intermediate network element with respect to a virtual path if that virtual path passes through that network element but does not originate or terminate at that network element. In the past, the intermediate network elements only switched virtual paths that passed through them. In other words, in past ATM networks the intermediate network elements did not add or remove virtual circuits to virtual paths.
Consider data originating at the network element 102. In order to send data from the network element 102 to any of the other three network elements shown in FIG. 1, there must be three virtual paths defined. The first virtual path 110 begins at the network element 102 and terminates at the network element 104 (it has no intermediate network elements). The second virtual path 112 begins at the network element 102, passes through network element 104 (which is an intermediate network element with respect to this virtual path), and then terminates at the network element 106. The third virtual path 114 begins at the network element 102, passes through the network elements 104 and 106 (both of which are intermediate network elements with respect to this virtual path), and then terminates at the network element 108. Each of the virtual paths 110, 112 and 114, may also be used to carry data backward from the destination network elements 104, 106 and 108 (respectively) to the source network element 102.
In this scheme, bandwidth management may be handled by the source network element of the virtual path (for example the network element 102 with respect to the virtual path 114). This may be done because the source network element 102 knows how much of the bandwidth assigned to the virtual path 114 is being used at any given time. Allowing the source network element to manage bandwidth provides for relatively simple bandwidth management. Alternatively, the destination network element of the virtual path may handle the bandwidth management (for example the network element 108 with respect to the virtual path 114). Allowing the destination network element 108 to manage bandwidth is slightly more complex because the destination network element 108 must signal backward to the source network element 102 when the virtual path 114 is carrying its maximum allotted bandwidth. This backward signaling would be necessary to prevent the source network element 102 from sending more cells than may be received by the destination network element 108 over the virtual path 114.
One problem with the conventional arrangement of virtual paths is the large number of virtual paths required to fully connect the network elements within the network. The number of virtual paths required to fully connect the network elements using past ATM techniques is nonlinear, being given by X*(N*(Nxe2x88x921))/2, where X is the number of QoS classes defined for the network and N is the number of network elements in the network. Even for moderately sized networks, where N may be on the order of one hundred, conventional arrangements of virtual paths may lead to a great deal of administrative complexity.
Another problem created by past virtual path arrangements is the fragmentation of bandwidth among the many virtual paths. Given the large number of network elements to be interconnected (and assuming a uniform community of interest amongst network elements) each virtual path is allocated a relatively small amount of the total bandwidth. The effect is to greatly reduce the amount of statistical multiplexing possible by any network element. The number of virtual paths running between each pair of adjacent network elements is X*N*(Nxe2x88x921)/2. As a result, since each virtual path is allocated a relatively small amount of the bandwidth at any given network element, the ability of that network element to perform statistical multiplexing is greatly reduced.
Yet another problem with past arrangements of virtual paths is inefficient call setup when the network elements are arranged in a ring topology. In order to set up a call between two network elements it is necessary to check bandwidth availability between each pair of network elements along the path from the source network element to the destination network element. This hop-by-hop approach to call setup is extremely inefficient.
The presence of these and other problems in past arrangements of virtual paths within ATM networks demonstrates that a need has long existed for an improved arrangement of virtual paths within an ATM network.
It is an object of the present invention to provide a new type of virtual path within an ATM network.
Another object of the present invention is to reduce the number of virtual paths required to fully connect the network elements of an ATM network, thereby simplifying bandwidth allocation and network administration.
Still another object of the present invention is to provide an arrangement of virtual paths within an ATM network that increases the effectiveness of statistical multiplexing within the network elements.
Yet another object of the present invention is to provide an arrangement of virtual paths within an ATM network that simplifies call setup.
One or more of the foregoing objects are met in whole or in part by a preferred embodiment of the present invention that provides a network topology for an ATM network. The topology includes a source network element, at least one intermediate network element, and a distributed virtual path connecting the source network element and the intermediate network elements. The distributed virtual path includes a virtual circuit that originates from the source network element and a virtual circuit that originates from at least one of the intermediate network elements. The distributed virtual path originates from the source network element and may terminate on a destination network element or on the source network element (thereby forming a ring) The network elements may be, for example, computers, satellites or other communications devices.